#coding=utf-8 
'''
Created on 2012-8-28
@author: gazhang
'''
#http://blog.csdn.net/v_JULY_v/article/details/6057286
#problem 11,16
class node:
	def __init__(self,_left_child,_right_child,_value):
		self._left=_left_child;
		self._right=_right_child;
		self.value=_value;
	def _print(self):
		print self.value;
	
def pre_order(nod):
	print "pre_order"
	_list=[];
	while(len(_list)!=0 or nod is not None):
		while(nod is not None):
			nod._print();
			_list.append(nod);
			nod=nod._left
		nod=_list.pop();
		nod=nod._right;

def mid_order(nod):
	print "mid_order"
	_list=[];
	while(len(_list)!=0 or nod is not None):
		while(nod is not None):
			_list.append(nod);
			nod=nod._left
		nod=_list.pop();
		nod._print();
		nod=nod._right;

def post_order(nod):
	print "post_order"
	pre=None;
	_list=[];
	while(len(_list)!=0 or nod is not None):
		while(nod is not None):
			_list.append(nod);
			nod=nod._left
		#right node is null or just visit
		nod=_list[len(_list)-1];
		if(nod._right is None or nod._right==pre):
			nod=_list.pop();
			nod._print();
			pre=nod;
			nod=None;
		else:
			nod=nod._right;

#第16题（树）：
#题目（微软）：
#输入一颗二元树，从上往下按层打印树的每个结点，同一层中按照从左往右的顺序打印。
def level_order(nod):
	print "level order"
	_list1=[]
	_list2=[]
	_list1.append(nod)
	while(len(_list1)!=0 or len(_list2)!=0):
		while(len(_list1)!=0):
			temp=_list1.pop()
			temp._print()
			if temp._left is not None:
				_list2.append(temp._left)
			if temp._right is not None:
				_list2.append(temp._right)
		while(len(_list2)!=0):
			temp=_list2[len(_list2)-1]
			_list2.pop()
			_list1.append(temp);

#verify whether 'parent' is the parent of the child 
def isChild(parent,child):
	if(child is None):
		return True
	elif(parent is None):
		return False
	elif(parent==child):
		return True
	else:
		return isChild(parent._left, child) or isChild(parent._right, child) 

#"<0":'parent' is not the parent of 'child'.">=0" is
def distance(parent,child):
	if not child or not parent:
		return -1
	elif parent==child:
		return 0
	else:
		leftDistance=distance(parent._left, child)
		if leftDistance>=0:
			return leftDistance+1
		rightDistance=distance(parent._right, child)
		if  rightDistance>=0:
			return rightDistance+1
		return -1
		
#find common parent of 'nod1' and 'nod2' in tree 'root'
def findNearestCommonParent(root,nod1,nod2):
	if not isChild(root, nod1) or not isChild(root, nod2):
		return None
	else:
		if isChild(root._left, nod1) and isChild(root._left, nod2):
			return findNearestCommonParent(root._left, nod1, nod2)
		elif isChild(root._right,nod1) and isChild(root._right, nod2):
			return findNearestCommonParent(root._right, nod1, nod2)
		else:
			return root
		
#in tree 'root',get the distance between any two nodes:'nod1' and 'nod2' 		
def distanceBetweenNode(root,nod1,nod2):
	parent=findNearestCommonParent(root, nod1, nod2)
	return distance(parent,nod1)+distance(parent, nod2)

#height of tree 'root'
def height(root):
	if not root:
		return -1
	else:
		return max(height(root._left),height(root._right))+1

#get max instance between any two node in tree 'root'
#第11题（树）求二叉树中节点的最大距离...  
def maxDistance(root):
	if not root:
		return -1
	else:
		return max(height(root._left)+height(root._right)+2,maxDistance(root._left),maxDistance(root._right))

#Mirror binary Tree
def mirror(root):
	_list=[]
	_list.append(root)
	while len(_list)!=0:
		head=_list.pop()
		if(head is not None):
			_left=head._left
			_right=head._right
			head._left=_right
			head._right=_left
			_list.append(_left)
			_list.append(_right)
	return root;

n8=node(None,None,8)
n7=node(None,None,7)
n6=node(None,None,6)
n5=node(n8,None,5)
n4=node(None,n7,4)
n3=node(n6,None,3)
n2=node(n4,n5,2)
n1=node(n2,n3,1)
print isChild(n1,n8)		
commonParent=findNearestCommonParent(n1, n7, n3)
if commonParent:
	print commonParent.value
print distanceBetweenNode(n1,n1,n6)
print height(n1)
print maxDistance(n1)